#ifndef _priority_queue_h_
#define _priority_queue_h_

#include<iostream>
#include<map>
#include<vector>
#include<functional>

template <typename Unique, typename Comparable>
struct Data
{        
    Unique k;
    Comparable d;
    Data(Unique k, Comparable d):k(k), d(d){}
    Data(const Data& d):k(d.k), d(d.d){}
    Data(const Data&& d):k(std::move(d).k), d(std::move(d).d){}
    void operator=(const Data& d){k = d.k; d = d.d;}
};

template <typename Unique, typename Comparable>
class PriorityQueue
{
public:
    void insert(Data<Unique, Comparable>& _x);
    void deleteMin();
    void buildHeap(std::vector<Data<Unique, Comparable> >& _input);
    void remove(Unique k);
    void modifyData(Unique k, Comparable d);
    void merge(const PriorityQueue<Unique, Comparable>& _H1, const PriorityQueue<Unique, Comparable>& _H2);

    PriorityQueue(int capacity = 1000);
    ~PriorityQueue();
    void describe();
private:
    static std::map<Unique, int> hashTable;
    std::vector<Data<Unique, Comparable>* > array;
    int currentSize;
    void percolateDown(int);
};

template <typename Unique, typename Comparable>
std::map<Unique, int> PriorityQueue<Unique, Comparable>::hashTable;

template <typename Unique, typename Comparable>
PriorityQueue<Unique, Comparable>::PriorityQueue(int capacity):currentSize(0), array(capacity){}

template <typename Unique, typename Comparable>
PriorityQueue<Unique, Comparable>::~PriorityQueue(){}

template <typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::insert(Data<Unique, Comparable>& _x)
{
    if(currentSize == array.size()-1)
        array.resize(array.size()*2);
    int hole = ++currentSize;
    array[0] = &_x; // for temporary storage
    for(; _x.d<array[hole/2]->d; hole/2)
    {
        array[hole] = array[hole/2];
        hashTable[array[hole]->k] = hole;
    }
    array[hole] = array[0];
    hashTable[_x.k] = hole;
}

template <typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::deleteMin()
{
    if(currentSize == 0)
    {
        std::cout << "Error! Heap Already Empty!" << std::endl;
    }
    // perlocateDown
    hashTable.erase(array[1]->k);
    array[1] = array[currentSize--];
    percolateDown(1);
}

template <typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::percolateDown(int ind)
{
    int hole = ind;
    int child;
    Data<Unique, Comparable>* temp = array[hole];
    for(; hole*2<=currentSize; hole = child)
    {
        child = 2*hole;
        
        if(child<currentSize && array[child+1]->d < array[child]->d)
            child++;
        if(array[child]->d < array[hole]->d)
        {
            array[hole] = array[child];
            hashTable[array[child]->k] = hole;
        }
        else
            break;
    }
    array[hole] = temp;
    hashTable[array[hole]->k] = hole;
}

template <typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::buildHeap(std::vector<Data<Unique, Comparable> >& _input)
{
    std::vector<Data<Unique, Comparable> > t(_input);
    currentSize = t.size();
    for(int i=0; i<=t.size(); ++i)
    {
        array[i+1] = &t[i];
        hashTable[array[i+1]->k] = i+1;
    }
    for(int i=currentSize/2; i>0; --i)
        percolateDown(i);
}

template <typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::remove(Unique k)
{
    if(hashTable.find(k)==hashTable.end())
        std::cout << "This element is not present!" << std::endl;
    else
    {
        int ind = hashTable[k];
        array[ind] = array[currentSize--];
        percolateDown(ind);
    }
}

template <typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::modifyData(Unique k, Comparable d)
{
    if(hashTable.find(k)==hashTable.end())
        std::cout << "This element is not present!" << std::endl;
    else
    {
        int ind = hashTable[k];
        array[ind]->d += d;
        if(array[ind]->d>array[ind*2] && ind*2<=currentSize)
        {
            percolateDown(ind);
        }
        else if(array[ind]->d<array[ind/2]->d)
        {
            array[0] = array[ind];
            for(; array[ind]->d<array[ind/2]->d; ind/2)
            {
                array[ind] = array[ind/2];
                hashTable[array[ind]->k] = ind;
            }
            array[ind] = array[0];
            hashTable[array[ind]->k] = ind;
        }
        else
            ; 
    }
}

template <typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::describe()
{
    typename std::vector<Data<Unique, Comparable>* >::iterator iter = array.begin();
    int ind = currentSize;
    int temp = 0;
    for(; iter!=array.end(); ++iter)
    {
        if(temp>=1 && temp <=currentSize)
            std::cout << (*iter)->d << " " << std::endl;
        else if(temp > currentSize)
            break;
        temp++;
    }
}

#endif